//找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。 
//
// 说明： 
//
// 
// 所有数字都是正整数。 
// 解集不能包含重复的组合。 
// 
//
// 示例 1: 
//
// 输入: k = 3, n = 7
//输出: [[1,2,4]]
// 
//
// 示例 2: 
//
// 输入: k = 3, n = 9
//输出: [[1,2,6], [1,3,5], [2,3,4]]
// 
// Related Topics 数组 回溯 
// 👍 392 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CombinationSumIii {
    public static void main(String[] args) {
        Solution solution = new CombinationSumIii().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 也比较常规的，而且有很多限定条件，遍历起来也就省事了很多
     * 必须保证剩余值为0而且size==k时才能添加
     * 进行了一个剪枝操作，剩余值较小时直接break
     * 而且dfs的时候也是直接传入了下一个数作为起始值，不会有重复的结果出现
     */
    class Solution {
        int k;
        int n;
        List<List<Integer>> res;
        List<Integer> temp;
        public List<List<Integer>> combinationSum3(int k, int n) {

            Map<Character, char[]> keyboard = new HashMap<>();
            keyboard.put('2',new char[]{'a','b','c'});


            this.k = k;
            this.n = n;
            res = new ArrayList<>();
            temp = new ArrayList<>();
            dfs(1,n);//一刷
            dfs(1,0,k,n,new ArrayList<Integer>());//二刷
            return res;
        }

        private void dfs(int begin, int target) {
            if (target == 0){
                if (temp.size()==k) res.add(new ArrayList<>(temp));
            }else {
                for (int i = begin; i <=9 ; i++) {
                    if (i > target) break;
                    temp.add(i);
                    dfs(i+1, target-i);
                    temp.remove(temp.size()-1);
                }
            }
        }

        //二刷，和一刷思路差不多
        public void dfs(int start, int sum, int k, int n, List<Integer> path){
            if(k == 0 && sum == n) res.add(new ArrayList(path));
            if(k > 0 && sum < n){
                for (int i = start; i <= n-sum && i <= 9; i++){
                    path.add(i);
                    dfs(i+1, sum+i, k-1, n, path);
                    path.remove(path.size()-1);
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}